#include <algorithm>

class Solution
{
public:
    int sumSubarrayMins(vector<int> &arr)
    {
        int n = arr.size();
        int *leftSide = new int[n]; // leftSide[i] 表示位置arr[i]左侧首个小于arr[i]的数的位置
        int *rightSide = new int[n]; // rightSide[i] 表示位置arr[i]右侧首个不大于arr[i]的数的位置

        vector<int> increaseStack;
        increaseStack.reserve(n);

        for (int i = 0; i < n; ++i)
        {
            while (!increaseStack.empty())
            {
                if (arr[increaseStack.back()] >= arr[i])
                {
                    increaseStack.pop_back();
                }
                else
                {
                    break;
                }
            }
            if (increaseStack.empty())
            {
                leftSide[i] = -1;
            }
            else
            {
                leftSide[i] = increaseStack.back();
            }
            increaseStack.push_back(i);
        }

        increaseStack.clear();
        for (int i = n - 1; i >= 0; --i)
        {
            while (!increaseStack.empty())
            {
                if (arr[increaseStack.back()] > arr[i])
                {
                    increaseStack.pop_back();
                }
                else
                {
                    break;
                }
            }
            if (increaseStack.empty())
            {
                rightSide[i] = n;
            }
            else
            {
                rightSide[i] = increaseStack.back();
            }
            increaseStack.push_back(i);
        }

        long long result = 0LL;
        for (int i = 0; i < n; ++i)
        {
            result += (arr[i] * static_cast<long long>(i - leftSide[i]) * static_cast<long long>(rightSide[i] - i)) % 1000000007LL;
        }
        result %= 1000000007LL;
        delete[] leftSide;
        delete[] rightSide;
        return static_cast<int>(result);
    }

private:
    int cutByMin(vector<int> &arr)
    {
        // 时间复杂度O(n^2)会超时
        using iterator = decltype(arr.cbegin());
        class SubSolution
        {
        public:
            long long sumSubarrayMins(const iterator &rangeBegin, const iterator &rangeEnd)
            {
                if (rangeBegin == rangeEnd)
                {
                    return 0LL;
                }
                iterator minElement = min_element(rangeBegin, rangeEnd);
                long long leftSize = minElement - rangeBegin;
                long long rightSize = rangeEnd - minElement - 1LL;
                long long sumMinsWithMinElement = (*minElement) * (1LL + leftSize) * (1LL + rightSize);
                // sumMinsWithMinElement = sumMinsWithMinElement % (1000000007LL);
                return (sumSubarrayMins(rangeBegin, minElement) + sumSubarrayMins(minElement + 1, rangeEnd) + sumMinsWithMinElement) % (1000000007LL);
            }
        };
        SubSolution s;
        return static_cast<int>(s.sumSubarrayMins(arr.cbegin(), arr.cend()));
    }
};